P1014 Cantor 表 — 题解思路

问题

按 Z 字形给对角线数表的每一项编号：第 1 项是 1/1，然后是 1/2、2/1、 3/1、2/2、……。给定编号 N，输出第 N 项对应的分数。

关键观察

每一项的分子、分母都是正整数，且编号是按 反对角线（分子 + 分母 之和 固定的那条斜线）分组、组内方向交替往返的：

• 第 k 条对角线（分子 + 分母 = k）恰有 k-1 项。
• 到第 k 条对角线为止，累计项数为 1 + 2 + ... + (k-1) = k*(k-1)/2。
• 对角线上第 pos 项（从 1 数）：
  • k 为奇数时分数从 1/(k-1) 走到 (k-1)/1，即分子 = pos，分母 = k-pos；
  • k 为偶数时从 (k-1)/1 走到 1/(k-1)，即分子 = k-pos，分母 = pos。

例如 N=7：到第 k=4 条对角线累计 6 项，故第 7 项落在 k=5 的第 1 位， 奇数对角线 → 1/4，与样例一致。

算法

1. 找到最小的 k 使 k*(k-1)/2 >= N；
2. 该对角线之前的项数为 (k-1)*(k-2)/2，于是本对角线上位置 pos = N - (k-1)*(k-2)/2；
3. 按 k 奇偶决定分子、分母，输出 分子/分母。

复杂度

• 求 k 用线性递增，k ≈ sqrt(2N)，对 N <= 10^7 至多几千次迭代； 也可以用二分或直接解二次方程得到 O(log N) / O(1)。
• 时间 O(sqrt(N))，空间 O(1)。

收获

学会把一个看似复杂的“蛇形 / 锯齿”枚举拆成「按对角线分组 + 组内方向交替」的 结构，再用等差数列求和 k*(k-1)/2 直接定位所在组与组内位置。